package sort;

import java.util.Arrays;

/**
 * @Classname InsertSort
 * @Author happytaohaha
 * @Date 2020/2/28
 * @Description 插入排序
 * 插入排序的复杂度还是O(n^2)
 * 但是比冒泡和比选择排序要好，速度要更快一些，因为插入排序使用了部分有序的队列作比较
 * 稳定
 */
public class InsertSort {
    public static int[] insertSort(int[] array) {
        int len = array.length;
        int temp;
        for(int i = 0; i < len-1; i++){
            for(int j = i+1; j > 0; j --){
                if(array[j] > array[j-1]){
                    break;
                }else{
                    temp = array[j];
                    array[j] = array[j-1];
                    array[j-1] = temp;
                }
            }
        }
        return array;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(insertSort(new int[]{5, 4, 3, 2, 1})));
    }
}
